#include "../tools.h"


// class Solution {
// public:
//     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//         /**
//          * 返回当前树下p 或 q的最近父节点
//          * 模拟一下
//          */
//         if (root == nullptr) return nullptr;
//         if (root == p || root == q) return root;

//         TreeNode* l = lowestCommonAncestor(root->left,  p, q);
//         TreeNode* r = lowestCommonAncestor(root->right, p, q);

//         if(l == nullptr) return r;
//         if(r == nullptr) return l;
//         if(l && r) return root; // ！p和q在两侧
//         return nullptr;
//     }
// };

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        /**
         * 返回当前树下p 或 q的最近父节点
         * 模拟一下
         */
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root;

        TreeNode* l = lowestCommonAncestor(root->left,  p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);

        if(l && r) return root; // ！p和q在两侧
        return l == nullptr ? r : l;
    }
};

int main(int argc, char const *argv[])
{
    
    vector<int> root = {3,5,1,6,2,0,8,-1,-1,7,4};
    int p = 5, q = 1;

    TreeNode* tree = create_tree(root);
    show(tree);
    cout << endl;

    TreeNode* nodep = get_tree_node(tree, p);
    // show(nodep);
    // cout << endl;
    TreeNode* nodeq = get_tree_node(tree, q);
    // show(nodeq);

    Solution s;
    TreeNode* res = s.lowestCommonAncestor(tree, nodep, nodeq);
    cout << res->val << endl;




    return 0;
}
